// https://leetcode.cn/problems/count-ways-to-build-good-strings/description/?envType=study-plan-v2&envId=dynamic-programming

// 算法思路总结：
// 1. 使用动态规划统计所有合法字符串数量
// 2. f[i]表示长度为i的合法字符串数量
// 3. 状态转移：通过添加zero个0或one个1从更短长度扩展
// 4. 累加low到high范围内所有长度的方案数
// 5. 时间复杂度：O(high)，空间复杂度：O(high)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int countGoodStrings(int low, int high, int zero, int one) 
    {
        const int MOD = 1000000007;
        
        int ret = 0;
        vector<int> f(high + 1); 
        f[0] = 1;
        for (int i = 1; i <= high; i++) 
        {
            if (i >= zero) f[i] = f[i - zero];
            if (i >= one)  f[i] = (f[i] + f[i - one]) % MOD;
            if (i >= low)  ret = (ret + f[i]) % MOD;
        }
        return ret;
    }
};

int main()
{
    int low1 = 3, high1 = 3, zero1 = 1, one1 = 1;
    int low2 = 2, high2 = 3, zero2 = 1, one2 = 2;

    Solution sol;

    cout << sol.countGoodStrings(low1, high1, zero1, one1) << endl;
    cout << sol.countGoodStrings(low2, high2, zero2, one2) << endl;

    return 0;
}